In the specific technical field of communication systems, such as communication system 100 shown in FIG. 1, it is well known that any message C comprising digital information can be processed and transferred from a system to another through electronic communication means which might be affected by noise.
In substance, a sequence x of Boolean symbols transmitted by a transmitter 102 through a communication channel 104 undergoing noise can be received at a receiver 106 as a different sequence y from which it is necessary to go back to the initial sequence x.
Traditionally, the sequence x of symbols to be transmitted comprises an additional or redundant portion including an error corrector code allowing the message, which is more probably the original even with errors, to be restored when received.
These error corrector codes are based on well known mathematical theories, such as for example the Hamming code theory, which are presently applied in several contexts wherein it is necessary to remedy noise in communication channels.
For a better understanding of all aspects of the present invention, a detailed description of the most used methods for correcting errors in digital information coded as symbol sequences in the Boolean logic is illustrated hereinafter.
0.1 Basic Definitions
Definition 1 Given m·n real numbers, a table like the following one is called matrix of the type [m×n]:
  M  =      (                                        a            11                                                a            12                                    ⋯                                      a                          1              ⁢              n                                                                        a            21                                                a            22                                    ⋯                                      a                          2              ⁢              n                                                            ⋮                                                                                                                          ⋮                                                  a            m1                                                a            m2                                    ⋯                                      a            mn                                )  
Definition 2 The transpose of the above matrix, indicated with MT, is the matrix:
         (                                        a            11                                                a            21                                    ⋯                                      a            m1                                                            a            12                                                a            22                                    ⋯                                      a            m2                                                ⋮                                                                                                                          ⋮                                                  a                          1              ⁢              n                                                            a                          2              ⁢              n                                                ⋯                                      a            mn                                )  obtained from M by exchanging, in order, rows with columns.
Definition 3 A n-×-n-order square matrix M is considered. Fixing an element aik of the matrix M and eliminating therein the row and the column crossing in the element (the i-th row and the k-th column) a square matrix of order (n−1)×(n−1) is obtained, whose determinant is called complementary minor of aik and will be indicated with Mik.
Definition 4 The determinant of the second order matrix is the number:a11a22−a12a21
Definition 5 The determinant of a n-order matrix is:
      ∑          k      =      1        n    ⁢                    a        ik            ·                        (                      -            1                    )                          i          -          k                      ⁢          M      ik      
Definition 6 The square matrix having 1 as elements aii and 0 elsewhere is called identity matrix and is indicated with I.
Definition 7 A group G is a set in which an operation * is defined, for which G is closed for *, i.e. if g ε G and h ε Gg*h ε G;    * is associative;    G has the identity, i.e. ∃ and ε G so that e*g=g*e=g∀gε G;    ∀g ε G the inverse exists, i.e. ∃g-1 ε G so that g-1*g=g*g-1=e.
Definition 8 If the operation * is the sum the group is called additive
Definition 9 A group is called abelian if the operation * is commutative
Definition 10 The set {0,1,2, . . . , p−1} is called remainder class (mod p) and is indicated with Zp, the property being that in these classes p=identity.
Definition 11 A Boolean group is a binary group, i.e. a group containing only the numbers 0 and 1 and 1+1=0.
Definition 12 A set of vectors v1, . . . , vk is linearly dependent if and only if there are some scalars c1, . . . , ck≠0 so that c1v1+c2v2+ . . . +ckvk=0.
Definition 13 A family of vectors is called base of the area if it is a generating family, i.e. any other vector of the area is a linear combination of these vectors, and it is composed of linearly independent vectors.
0.1.1 Codes
The aim of the self-corrector code theory, a branch of the information theory, was originally born to solve some practical problems in the communication of coded digital information. A message is considered as a block of symbols of a finite alphabet; it is usually a sequence of 0 and 1 but it can be also any number, a letter or a complete sentence. The message is transmitted through a communication channel undergoing a noise. The aim of the self-corrector code theory is to add redundant terms to the message so that it is possible to go back to the original message if the transmitted message has been damaged. First of all, a difference must be made between diagnosing and correcting errors. Diagnostics detects the presence of an error, while the correction detects and corrects the error.
Each message called c consists of k information digits. The coding turns, according to certain rules, each input message c into a binary nth number x with n>k.
This binary nth number x is the code word of the message c. During the transmission some errors can occur, the binary nth number y being thus receivedc→x→channel→y
The area V of all nth numbers of 0 and 1 will be now considered adding component vectors per module component 2.
Definition 14 A linear binary code [n,k] is the set of all linear combinations of k(≠0) independent vectors in V. Linear means that if two or more vectors are in the code, also their sum is therein.
Definition 15 A generating matrix G for a linear code is a matrix k×n whose rows are a base for C.
Definition 16 A parity matrix H of a linear code is a matrix n×k so that G·H=0.
Definition 17 H is the parity matrix of a code C w·ε C if and only if wHT=0.
Definition 18 G is called in standard form if G=(IkP) where Ik is the identity matrix k×k and P is a matrix k×(n−k). If G is in the systematic or standard form, then the first k symbols of a word are called information symbols.
Theorem 19 If a code C [n,k] has a matrix G=(IkP) in the standard form, then a C parity matrix is H=(−PTIn−k) where pT is the transpose of P and is a matrix (n−k)×k and In−k is the identity matrix (n−k)×(n−k)
Systematic codes have the advantage that the data message is in the code word and it can be read before decoding. For codes in the non-systematic form the message is no more recognizable in the coded sequence and an inverter is needed to recognize the data sequence.
Definition 20 Being C a linear code with parity matrix H, then, given x a binary nth number xHT, is called syndrome of x.
Definition 21 The weight of a vector u is the number of component being different from 0.
Definition 22 The code minimum weight d is the weight of the vector different from 0 having the lowest weight in the code.
d is thus a measure of the “quality” of a code.
Defined a sphere Sr(u) with radius r around a vector u like Sr(u)={vεV|d(u,v)≧r}
Theorem 23 If d is the minimum weight of a code C, then C can correct at most
  t  =      [                  d        -        1            2        ]  errors and vice versa.
Corollary 24 C has a minimum weight d if d is the highest number so that each d−1 columns of the parity matrix H are independent.
Supposing for example that a code in the systematic form correcting 2 errors is to be produced. The matrix H will be composed of the identity matrix and of a matrix PT having 4 linearly independent columns, i.e. so that the determinant of the sub-matrix composed of these four columns ≠0. Therefore, according to the number of errors to be corrected, a matrix H with d−1 linearly independent columns is searched. Therefore, given n and k, a code with d being the widest possible is searched in order to correct more errors.
It is however possible to have vectors in V which are not comprised in any of these spheres.
Definition 25 A minimum-weight-d code C is called perfect if all vectors in V are comprised in
      spheres    ⁢                  ⁢    of    ⁢                  ⁢    radius    ⁢                  ⁢    t    =      [                  d        -        1            2        ]  around the code words. In this case it can be said that the spheres cover the area.For the given n and k they are the best codes.
Theorem 26 For a perfect binary code [n,k] to exist, n, k and t must satisfy the following equation
            (                        (                                                    n                                                                    0                                              )                +                  (                                                    n                                                                    1                                              )                +        ⋯        +                  (                                                    n                                                                    t                                              )                    )        ⁢          2      k        =      2    n  Generally,
Theorem 27 For a code [n,k] to exist, n, k and t must satisfy the following inequality known as Hamming inequality:
            (                        (                                                    n                                                                    0                                              )                +                  (                                                    n                                                                    1                                              )                +        ⋯        +                  (                                                    n                                                                    t                                              )                    )        ⁢          2      k        ≥      2    n  
When the word y is received the word x being sent and afterwards the data message c are to be searched. With the following formula: y=x+ξtH(m+ξt)=Hξt where ξt is a particular error class. If Hξt ε H, then it can be said which is the wrong position.
Supposing that an error occurs:m+ξiH(m+ξi)=HξiHξi ε H?→wrong position: i
Supposing now that two errors occur:m+ξi+ξjH(m+ξ+ξj)=Hξi+Hξj=s∀ξi→Hξi+Hξj ε H?→wrong positions: i and j
The following practical example for corrector codes of one error (Hamming codes) is now examined: the Hamming code [7,4] described by the following generating matrix is considered:
  G  =      (                            1                          0                          0                          0                          0                          1                          1                                      0                          1                          0                          0                          1                          0                          1                                      0                          0                          1                          0                          1                          1                          0                                      0                          0                          0                          1                          1                          1                          1                      )  
The first 4 positions are considered as the information positions and the last 3 positions as redundancy positions. Therefore the first row is the message 1 0 0 0 and so on. All words are obtained by adding (mod 2) those rows. For example the message u=(1011) is coded as x=
  H  =      (                            0                          0                          0                          1                          1                          1                          1                                      0                          1                          1                          0                          0                          1                          1                                      1                          0                          1                          0                          1                          0                          1                      )  (1011010). The parity matrix H is considered:
It must be noted that the matrix columns have been written so that the i-th column is composed of 2-based i-development coefficients, in case completed by 0.
Supposing to send the message x above and that an error occurs. The message y=(1010010) is thus received. The syndrome is calculated:HyT=(100)(1 0 0) is the binary representation of 4; the wrong bit is therefore the fourth.
The ideal is thus to search perfect codes, but they are not always found, moreover codes recognizing an error of the 0→1 type from 1→0 are wished.
Although advantageous under many aspects, the methods presently used require adding a redundancy information portion which, the size of the single message to be coded being fixed, cannot be lower than a minimum indicated. A technical problem underlying embodiments of the present invention is to provide a linear code protecting digital information coded like binary symbol sequences and overcoming the limits of the solutions presently provided by the prior art.